package com.leetcode.算法策略相关.动态规划;

/**
 * @author: xiaomi
 * @date: 2021/2/6
 * @description: 53. 最大子序和
 * https://leetcode-cn.com/problems/maximum-subarray/
 */
public class A_53_最大子序和 {


    public static void main(String[] args) {

    }

    /**
     * 最长连续子序列（由于限制了元素的大小，所以不需要考虑越界的问题）
     * --
     * to be honest,一开始真的很难想得到 DP 的状态和转移方程。
     * 所以，我只能用 force
     *
     * @param nums
     * @return
     */
    public int maxSubArrayByForce(int[] nums) {
        int len = nums.length;
        int res = Integer.MIN_VALUE;
        int partSum = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                partSum += nums[j];
                res = Math.max(res, partSum);
            }
            partSum=0;
        }
        return res;
    }
}
